'''
@Descripttion: 顺序不一样，结果不一样，[1, 2] != [2, 1]
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-17 11:15:49
LastEditTime: 2025-09-18 16:56:40
'''



class Solution:

    def combinationSum4(self, nums, target):

        # def dfs(i, t):
        #     if i < 0:
        #         return 1 if target == 0 else 0
            
        #     if t < nums[i]:
        #         return dfs(i - 1, t)

        #     return  dfs(i - 1, t) + dfs(i, t - nums[i])
        
        # return dfs(len(nums) - 1, target)
        @cache
        def dfs(target):
            if target == 0:
                return 1
            elif target < 0:
                return 0
            ans = 0
            for n in nums:
                ans = ans + dfs(target - n)
            
            return ans

        return dfs(target)

        # for n in nums:



